package org.czl.leetcode4;

import java.util.PriorityQueue;

public class ll3342 {
    public static void main(String[] args) {
        System.out.println(minTimeToReach(new int[][]{{0, 4}, {4, 4}}));
        System.out.println(1);
    }
    //分层图中的djk算法
    static int[] up = new int[]{1, -1 ,0, 0};
    static int[] down = new int[]{0,0, - 1, 1};
    public static int minTimeToReach(int[][] moveTime) {
        int m = moveTime.length;
        int n = moveTime[0].length;
        //最后一维0 表示偶数走到位置时的最短距离, 1表示奇数走过去的最短距离;
        int[][][] dis = new int[m][n][2];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                dis[i][j][1] = Integer.MAX_VALUE;
                dis[i][j][0] = Integer.MAX_VALUE;
            }
        }
        dis[0][0][0] = 0;
        boolean[][][] set = new boolean[m][n][2];
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[3] - b[3]);
        queue.add(new int[]{0,0,0,0});
        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            if(set[cur[0]][cur[1]][cur[2]]){
                continue;
            }
            set[cur[0]][cur[1]][cur[2]] = true;
            for(int i = 0; i < 4; i++){
                int fx = cur[0] + up[i];
                int fy = cur[1] + down[i];
                int f;
                if(cur[2] == 1){
                    f = 0;
                }else{
                    f = 1;
                }
                if(fx >= 0 && fy >= 0 && fx < m && fy < n && !set[fx][fy][f]){
                    int step;
                    if(cur[2] == 0){
                        step = 1;
                    }else{
                        step = 2;
                    }
                    int time = Math.max(moveTime[fx][fy], cur[3]);
                    if(dis[fx][fy][f] > time + step){
                        dis[fx][fy][f] = time + step;
                        queue.add(new int[]{fx, fy, f, time + step});
                    }
                }
            }
        }
        if(dis[m - 1][n - 1][0] == Integer.MAX_VALUE)return dis[m - 1][n - 1][1];
        if(dis[m - 1][n - 1][1] == Integer.MAX_VALUE)return dis[m - 1][n - 1][0];
        return Math.max(dis[m - 1][n - 1][0], dis[m - 1][n - 1][1]);
    }
}
